package leetcode.t4LinkedList;

/**
 * @author K
 * @date 2024/1/23 13:43
 */
public class T148_SortList {


    /**
     * 148. 排序链表
     *
     * @param head
     * @return
     */
    public static ListNode sortList(ListNode head) {
        if (head == null || head.next == null)
            return head;
        ListNode fast = head.next, slow = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode tmp = slow.next;
        slow.next = null;
        ListNode left = sortList(head);
        ListNode right = sortList(tmp);
        ListNode dummy = new ListNode(0);
        ListNode result = dummy;
        while (left != null && right != null) {
            if (left.val < right.val) {
                dummy.next = left;
                left = left.next;
            } else {
                dummy.next = right;
                right = right.next;
            }
            dummy = dummy.next;
        }
        dummy.next = left != null ? left : right;
        return result.next;
    }

    /**
     * 友好格式
     */
    public ListNode sortList2(ListNode head) {
        //1递归结束条件
        if (head == null || head.next == null) {
            return head;
        }

        //2找到中间节点，分成2半
        ListNode slow = getMiddleNode(head);
        ListNode fast;
        fast = slow.next;
        slow.next = null;

        //再继续分
        ListNode left = sortList2(head);
        ListNode right = sortList2(fast);

        //3业务处理，合并链表
        return mergeTwoList(left, right);
    }


    private ListNode mergeTwoList(ListNode left, ListNode right) {
        ListNode dummy = new ListNode(1);
        ListNode result = dummy;
        while (left != null && right != null) {
            if (left.val < right.val) {
                dummy.next = left;
                left = left.next;
            } else {
                dummy.next = right;
                right = right.next;
            }
            dummy = dummy.next;
        }

        dummy.next = left != null ? left : right;
        return result.next;
    }

    /**
     * 获取中间节点 快慢指针
     *
     * @param head
     * @return
     */
    private ListNode getMiddleNode(ListNode head) {
        ListNode slow = head;
        ListNode fast = head.next.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = slow.next.next;
        }
        return slow;
    }

    public static void main(String[] args) {
        ListNode listNode = new ListNode(4);
        ListNode listNode1 = new ListNode(2);
        ListNode listNode2 = new ListNode(1);
        ListNode listNode3 = new ListNode(3);
        listNode.next = listNode1;
        listNode1.next = listNode2;
        listNode2.next = listNode3;

        ListNode result = sortList(listNode);
    }

}
